package com.flute.icrawler.framework.framework.container;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

import com.flute.icrawler.framework.framework.CrawlUrl;

public class AdditionalUrlQueue {

	private List<CrawlUrl> additionalList;
	private HashSet<String> urlSet;

	public AdditionalUrlQueue() {
		this.additionalList = new ArrayList<CrawlUrl>();
		this.urlSet = new HashSet<String>();
	}

	public synchronized void addCrawlUrl(CrawlUrl additional) {
		this.urlSet.add(additional.getUrl());

		if (additionalList.size() > 0) {
			int position = getPosition(additional, 0, additionalList.size());
			additionalList.add(position, additional);
		} else {
			additionalList.add(additional);
		}
	}

	/**
	 * 返回第一个url.
	 * 如果url不在urlSet中，则说明url已经被重复添加，并且排在前面的url已经被处理过，则排在后面的相同的url直接跳过，不做处理。
	 * 因为辅助信息的变化可能导致排序的变化，因此应该允许有重复的url添加进来，但是对于重复的url，我们只处理第一个
	 * 
	 * @return
	 */
	public synchronized CrawlUrl getFirstCrawlUrl() {
		if (additionalList.size() > 0) {
			CrawlUrl result = additionalList.get(0);
			additionalList.remove(0);

			while (!urlSet.contains(result.getUrl())) {
				if (additionalList.size() > 0) {
					result = additionalList.get(0);
					additionalList.remove(0);
				} else {
					return null;
				}
			}

			urlSet.remove(result.getUrl());

			return result;
		} else {
			return null;
		}
	}

	public boolean containsUrl(String url) {
		return urlSet.contains(url);
	}

	public int size() {
		return urlSet.size();
	}

	private int getPosition(IAdditional additional, int low, int up) {
		int middlePosition = (low + up) / 2;
		IAdditional middle = additionalList.get(middlePosition);

		if (low == up) {
			return low;
		}
		if (up - low == 1) {
			if (additional.getAdditionalUrlInformation().compareTo(
					middle.getAdditionalUrlInformation()) == 0) {
				return middlePosition;
			} else if (additional.getAdditionalUrlInformation().compareTo(
					middle.getAdditionalUrlInformation()) > 0) {
				return up;
			} else if (additional.getAdditionalUrlInformation().compareTo(
					middle.getAdditionalUrlInformation()) < 0) {
				return low;
			}
		} else {
			if (additional.getAdditionalUrlInformation().compareTo(
					middle.getAdditionalUrlInformation()) == 0) {
				return middlePosition;
			} else if (additional.getAdditionalUrlInformation().compareTo(
					middle.getAdditionalUrlInformation()) > 0) {
				middlePosition = getPosition(additional, middlePosition, up);
			} else if (additional.getAdditionalUrlInformation().compareTo(
					middle.getAdditionalUrlInformation()) < 0) {
				middlePosition = getPosition(additional, low, middlePosition);
			}
		}

		return middlePosition;
	}
}
